﻿/*
 * Module Name: RBTree.cs
 * 
 * Purpose: This is an implementation of a Red Black Tree
 * 
 * Created by: Chris Tisdale
 */

using System;
using System.Collections.Generic;
using System.Text;

namespace Common_Code.Trees
{
    class RBTree<T> : Tree<T> where T : IComparable
    {
        /*
         * These are the private variables used throught the function
         */
        private Node<T> headNode;
        private T[] treeInArray;
        private bool change = true;
        private int size = 0;

        /*
         * Name: RBTree
         * 
         * Parameters: Node<T> head
         * 
         * Returns: A RBTree Object
         * 
         * Purpose: Creates a red black tree
         */
        public RBTree(Node<T> head)
        {
            headNode = head;
        }

        /*
         * Name: RBTree
         * 
         * Parameters: None
         * 
         * Returns: A RBTree Object
         * 
         * Purpose: Creates a red black tree
         */
        public RBTree()
        {
            headNode = null;
        }

        /*
         * Name: AddNode
         * 
         * Parameters: T item
         * 
         * Returns: None
         * 
         * Purpose: Adds an item to the tree
         */
        public void AddNode(T item)
        {
            throw new NotImplementedException();
        }

        /*
         * Name: DeleteNode
         * 
         * Parameters: T item
         * 
         * Returns: None
         * 
         * Purpose: If the item was removed true is returned, else false is returned
         */
        public void DeleteNode(T item)
        {
            throw new NotImplementedException();
        }

        /*
         * Name: FindItem
         * 
         * Parameters: T item
         * 
         * Returns: Node
         * 
         * Purpose: This gives you all of the elements from the tree
         */
        public Node<T> FindItem(T item)
        {
            return FindRec(headNode, item);
        }

        /*
         * Name: FindRec
         * 
         * Parameters: Node<T> node
         *             T item
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a recursive function that returns the Node which contains the item
         */
        private Node<T> FindRec(Node<T> node, T item)
        {
            if (node == null)
                return null;
            var comp = item.CompareTo(node.GetItem());
            if (comp > 0)
            {
                return FindRec(node.GetRightNode(), item);
            }
            else if (comp < 0)
            {
                return FindRec(node.GetLeftNode(), item);
            }
            else
            {
                //found item
                return node;
            }
        }

        /*
         * Name: ToArray
         * 
         * Parameters: NA
         * 
         * Returns: T[]
         * 
         * Purpose: This gives you all of the elements from the tree
         */
        public T[] ToArray()
        {
            if (change)
            {
                treeInArray = new T[size];
                CreateArray(headNode, 0);
                change = false;
            }
            return treeInArray;
        }

        /*
         * Name: CreateArray
         * 
         * Parameters: Node<T> node
         *             int loc
         * 
         * Returns: Node<T>
         * 
         * Purpose: This is a recursive function creates an array from the tree
         */
        private Node<T> CreateArray(Node<T> node, int loc)
        {
            if (node == null)
                return null;
            CreateArray(node.GetLeftNode(), loc);
            treeInArray[loc] = node.GetItem();
            loc++;
            CreateArray(node.GetRightNode(), loc);
            return node;
        }
    }
}
